/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Apr 14, 2014
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given two binary trees, write a function to check if they are
 *              equal or not.
 * 
 *              Two binary trees are considered equal if they are structurally
 *              identical and the nodes have the same value.
 */
public class SameTree {

	private class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	public boolean isSameTree(TreeNode p, TreeNode q) {
		if (null == p && null == q)
			return true;
		else if (null == p || null == q)
			return false;

		if (p.val == q.val)
			return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
		else
			return false;
	}

	@Test
	public void test() {
		TreeNode n1 = new TreeNode(1);
		TreeNode n2 = new TreeNode(2);
		TreeNode n3 = new TreeNode(3);
		TreeNode n4 = new TreeNode(4);
		TreeNode n5 = new TreeNode(5);
		TreeNode n6 = new TreeNode(6);
		n1.left = n2;
		n1.right = n3;
		n2.left = n4;
		n4.left = n5;
		n4.right = n6;

		// List<List<Integer>> res = levelOrderBottom(n1);
		// for (List<Integer> list : res) {
		// for (int i : list) {
		// System.out.print(i + ",");
		// }
		// System.out.println();
		// }
		assert isSameTree(n1, n1);
		assert !isSameTree(n1, n2);
	}
}
